package alg.search;

/*
* 计算中点索引
 ，其中
 表示向下取整操作。
判断 nums[m] 和 target 的大小关系，分为以下三种情况。
当 nums[m] < target 时，说明 target 在区间
 中，因此执行
 。
当 nums[m] > target 时，说明 target 在区间
 中，因此执行
 。
当 nums[m] = target 时，说明找到 target ，因此返回索引
 。
若数组不包含目标元素，搜索区间最终会缩小为空。此时返回
 。
 * */
public class BinarySearch {

    public static int binarySearch(int[] nums, int target) {
        int i=0,j=nums.length-1; ;
        while (i <= j) {
            int middle=(i+j)/2;
            if (nums[middle] < target) {
                i=middle+1;
            }else if (nums[middle]>target){
                j=middle-1;
            }else {
                j= middle-1;
            }

        }
        return i;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,6,6,6,8,12,15,23,26,31,42};
        int target = 6;

        int result = BinarySearch.binarySearch(nums, target);
        System.out.println(result);
    }
}
/*
二分查找仅适用于有序数据。
二分查找仅适用于数组。二分查找需要跳跃式（非连续地）访问元素，而在链表中执行跳跃式访问的效率较低，因此不适合应用在链表或基于链表实现的数据结构。
小数据量下，线性查找性能更佳。在线性查找中，每轮只需 1 次判断操作；而在二分查找中，需要 1 次加法、1 次除法、1 ~ 3 次判断操作、1 次加法（减法），共 4 ~ 6 个单元操作；因此，当数据量
 较小时，线性查找反而比二分查找更快。
* */